#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct TreeNode
{
	char data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
	int flag;
}TreeNode;
typedef struct StackNode 
{
	TreeNode* data;
	struct StackNode* next;
}StackNode;
void creatTree(TreeNode** T,int* index,char* data)
{
	char ch;
	ch = data[*index];
	(*index)++;
	if (ch == '#')
		*T = NULL;
	else
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		(*T)->flag = 0;
		creatTree(&((*T)->lchild), index, data);
		creatTree(&((*T)->rchild), index, data);
	}
}
StackNode* initStack()
{
	StackNode* s = (StackNode*)malloc(sizeof(StackNode));
	s->data = NULL;
	s->next = NULL;
	return s;
}
void headpush(TreeNode* data, StackNode* s)
{
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->data = data;
	node->next = s->next;
	s->next = node;
}
int is_empty(StackNode* s)
{
	if (s->next == NULL)
		return 1;
	else
		return 0;
}
StackNode* pop(StackNode* s)
{
	if (is_empty(s))
		return NULL;
	else
	{
		StackNode* node = s->next;
		s->next = node->next;
		return node;
	}
}
void preOrder(TreeNode* t)
{
	TreeNode* node = t;
	StackNode* s = initStack();
	while (node || !is_empty(s))
	{
		if (node)
		{
			printf("%c ", node->data);
			headpush(node, s);
			node = node->lchild;
		}
		else
		{
			node = pop(s)->data;
			node = node->rchild;
		}
	}
}
void inOrder(TreeNode* t)
{
	TreeNode* node = t;
	StackNode* s = initStack();
	while (node || !is_empty(s))
	{
		if (node)
		{
			headpush(node, s);
			node = node->lchild;
		}
		else
		{
			node = pop(s)->data;
			printf("%c ", node->data);
			node = node->rchild;
		}
	}
}
StackNode* getTop(StackNode* s)
{
	if (is_empty(s))
		return NULL;
	else
	{
		StackNode* node = s->next;
		return node;
	}
}
void postOrder(TreeNode* t)
{
	TreeNode* node = t;
	StackNode* s = initStack();
	while (node || !is_empty(s))
	{
		if (node)
		{
			headpush(node, s);
			node = node->lchild;
	    }
		else
		{
			TreeNode* top = getTop(s)->data;
			if (top->rchild && top->rchild->flag == 0) 
			{
				top = top->rchild;
				headpush(top, s);
				node = top->lchild;
			}
			else
			{
				top = pop(s)->data;
				printf("%c ", top->data);
				top->flag = 1;
			}
		}
	}
}
int main()
{
	int index = 0;
	TreeNode* t;
	char data[100];
	gets_s(data);
	creatTree(&t, &index, data);
	preOrder(t);
	printf("\n");
	inOrder(t);
	printf("\n");
	postOrder(t);
	return 0;
}